|
|
Computational and structural apects of interval graphs and their variants
Novotná, Jana ; Kratochvíl, Jan (vedoucí práce) ; Jelínek, Vít (oponent)
Intervalové grafy, průnikové grafy úseček (intervalů) na reálné přímce, hrají klíčovou roli při studování algoritmů a specifických strukturálních vlastností. Velmi studovanou třídou jsou také jednotkové intervalové grafy, vlastní podtřída intervalových grafů, kde každý interval má jednotkovou délku. V práci se věnu- jeme smíšeným jednotkovým intervalovým grafům, grafům vzniklým zobecněním jednotkových intervalových grafů, kde každý interval má stále jednotkovou délku, ale může být různého typu (uzavřený, otevřený, polouzavřený). Tato drobná modi- fikace zahrnuje výrazně širší třídu grafů, například smíšené jednotkové intervalové grafy nejsou na rozdíl od jednotkových grafů spáruprosté. Heggernes, Meister a Papadopoulos přišli s bublinkovým modelem, takovou reprezentací jednotkových intervalových grafů, která se jeví užitečná při konstrukci různých algoritmů. Tento model rozšiřujeme na třídu smíšených intervalových grafů. Původní bublinkový model využili autoři Boyaci, Ekim a Shalom, kteří s jeho pomocí dokazovali, že problém největšího řezu v jednotkovém intervalovém grafu je polynomiální. V jejich důkazu jsme však objevili nejspíše neopravitelnou chybu. Dalším přínosem práce jsou ukázky využití našeho rozšířeného bublinkového mod- elu, na němž stavíme subexponenciální algoritmus pro problém největšího řezu...
|
host ::
RSS.